package DP.斐波那契;

import org.junit.Test;

import java.time.LocalDateTime;
import java.util.HashMap;
import java.util.Map;

/**
 * 题干：第N个数=几
 *
 * vi (i)
 * if
 * 体
 * {ir} f(餐)
 *
 * 跑
 *
 * -----------------
 *
 * int f(5)
 *
 * if i=1or2
 * return 1
 *
 * r f(n-1)+f(n-2)
 *
 */
public class 斐波那契数列_剑10_1 {

    public int fib(int n) {
        if(n==1 || n==2){
            return 1;
        }
        return (fib(n-1) + fib(n-2)) % 1000000007;
    }

    Map<Integer, Integer> map = new HashMap<>();
    {map.put(1,1);map.put(2,1);}
    public int fibByMap(int n){
        if(n==0)return 0;
        if(n==1 || n==2)
            return 1;
        int res = ((map.containsKey(n-1)?map.get(n-1):fibByMap(n-1) )+
                (map.containsKey(n-2) ? map.get(n-2) : fibByMap(n-2))) % 1000000007;
        map.put(n, res);
        return res;
    }

    /**
     * dp
     *
     * @param n
     * @return
     */
    public int fibByDP(int n){
        if(n==0)
            return 0;
        if(n<2){
            return 1;
        }

        int[] dp = new int[n+1];
        dp[0]=0; dp[1]=1; dp[2]=1;
        for (int i = 3; i < n+1; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 1000000007;
        }
        return dp[n];
    }
    public int fibByDPAndCutSpace(int n){
        if(n==0)return 0;
        if(n==1 || n==2)return 1;

        int one = 1; int two = 1;
        for (int i = 0; i < n-2; i++) {
            int tmp = two;
            two = (one + two) % 1000000007;
            one = tmp;
        }
        return two;
    }
    @Test
    public void t(){
        System.out.println(LocalDateTime.now());
        System.out.println(fib(45)); // 1 1 2 3 5 8
        System.out.println(LocalDateTime.now());

        System.out.println(LocalDateTime.now());
        System.out.println(fibByMap(10000)); // 1 1 2 3 5 8
        System.out.println(LocalDateTime.now());

        System.out.println(LocalDateTime.now());
        System.out.println(fibByDP(10000)); // 1 1 2 3 5 8
        System.out.println(LocalDateTime.now());

        System.out.println(LocalDateTime.now());
        System.out.println(fibByDPAndCutSpace(10000)); // 1 1 2 3 5 8
        System.out.println(LocalDateTime.now());
    }
}
